package leetcode.code1404;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public String stoneGameIII(int[] stoneValue) {
		int n = stoneValue.length;
		int[] dp = new int[n + 1];
		int[] s = new int[n];
		for (int i = n - 1; i >= 0; i--) {
			int ans1 = stoneValue[i];
			int ans2 = Integer.MIN_VALUE;
			int ans3 = Integer.MIN_VALUE;
			if (i + 1 < n) {
				ans1 += s[i + 1] - dp[i + 1];
				ans2 = stoneValue[i] + stoneValue[i + 1];
			}
			if (i + 2 < n) {
				ans2 += s[i + 2] - dp[i + 2];
				ans3 = stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2];
			}
			if (i + 3 < n) {
				ans3 += s[i + 3] - dp[i + 3];
			}
			dp[i] = Math.max(Math.max(ans2, ans1), ans3);
			s[i] = stoneValue[i];
			if (i + 1 < n) {
				s[i] += s[i + 1];
			}
		}
		if (dp[0] * 2 == s[0]) {
			return "Tie";
		}
		return dp[0] * 2 > s[0] ? "Alice" : "Bob";
	}

	@Override
	public void debug4() {
		H.compare("Bob", this.stoneGameIII(H.str2array3("[1,2,3,7]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
